SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>PatchMatch</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">PatchMatch</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}html body.mediawiki .mw-parser-output .metadata.ambox{border-left:10px solid #36c!important;background-color:var(--background-color-neutral-subtle,#fbfbfb)!important}html body.mediawiki .mw-parser-output .metadata.ambox-speedy{border-left:10px solid #b32424!important;background-color:var(--background-color-destructive-subtle,#fee7e6)!important}html body.mediawiki .mw-parser-output .metadata.ambox-delete{border-left:10px solid #b32424!important}html body.mediawiki .mw-parser-output .metadata.ambox-content{border-left:10px solid #f28500!important}html body.mediawiki .mw-parser-output .metadata.ambox-style{border-left:10px solid #fc3!important}html body.mediawiki .mw-parser-output .metadata.ambox-move{border-left:10px solid #9932cc!important}html body.mediawiki .mw-parser-output .metadata.ambox-protection{border-left:10px solid #a2a9b1!important}.mw-parser-output .ambox.mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p><b>PatchMatch</b> is an <a href="Algorithm" title="Algorithm">algorithm</a> used to quickly find <a href="Correspondence_problem" title="Correspondence problem">correspondences</a> (or matches) between small square regions (or patches) of an <a href="Image" title="Image">image</a>. It has various applications in image editing, such as reshuffling or removing objects from images or altering their <a href="Aspect_ratio_(image)" title="Aspect ratio (image)">aspect ratios</a> without cropping or noticeably stretching them. PatchMatch was first presented in a 2011 paper by researchers at <a href="Princeton_University" title="Princeton University">Princeton University</a>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

<p>The goal of the <a href="Algorithm" title="Algorithm">algorithm</a> is to find the patch correspondence by defining a <b>nearest-neighbor field (NNF)</b> as a <a href="Function_(mathematics)" title="Function (mathematics)">function</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:\mathbb {R} ^{2}\to \mathbb {R} ^{2}}">

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:\mathbb {R} ^{2}\to \mathbb {R} ^{2}}</annotation>

</semantics>

</math></span><img src="./25c44be73c93794e647a2a66e3fc18f527395064.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.294ex; height:3.009ex;" alt="{\displaystyle f:\mathbb {R} ^{2}\to \mathbb {R} ^{2}}" loading="lazy"></span> of offsets, which is over all possible matches of patch (location of patch centers) in image A, for some distance function of two patches <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math></span><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy"></span>. So, for a given patch coordinate <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math></span><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span> in image <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> and its corresponding nearest neighbor <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math></span><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"></span> in image <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math></span><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(a)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(a)}</annotation>

</semantics>

</math></span><img src="./368cb4b81ba5754d7a354a4ce49c2f1084bdaace.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.318ex; height:2.843ex;" alt="{\displaystyle f(a)}" loading="lazy"></span> is simply <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b-a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b-a}</annotation>

</semantics>

</math></span><img src="./ecca61f9c918fe1deb227ed79d4979d70c443ea4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.068ex; height:2.343ex;" alt="{\displaystyle b-a}" loading="lazy"></span>. However, if we search for every point in image <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math></span><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span>, the work will be too hard to complete. So the following algorithm is done in a <a href="Randomness" title="Randomness">randomized</a> approach in order to accelerate the <a href="Calculation" title="Calculation">calculation</a> speed.

The algorithm has three main components. Initially, the nearest-neighbor field is filled with either random offsets or some prior information. Next, an iterative update process is applied to the NNF, in which good patch offsets are propagated to adjacent pixels, followed by random search in the neighborhood of the best offset found so far. Independent of these three components, the algorithm also uses a coarse-to-fine approach by building an <a href="Pyramid_(image_processing)" title="Pyramid (image processing)">image pyramid</a> to obtain the better result.

</p>

<div class="mw-heading mw-heading3"><h3 id="Initialization">Initialization</h3></div>

<p>When initializing with random offsets, we use independent <a href="Uniform" title="Uniform">uniform</a> <a href="Sample_(statistics)" class="mw-redirect" title="Sample (statistics)">samples</a> across the full range of image <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math></span><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span>. This algorithm avoids using an initial guess from the previous level of the pyramid because in this way the algorithm can avoid being trapped in <a href="Maxima_and_minima" class="mw-redirect" title="Maxima and minima">local minima</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Iteration">Iteration</h3></div>

<p>After initialization, the algorithm attempted to perform <a href="Iteration" title="Iteration">iterative</a> process of improving the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle NNF}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle NNF}</annotation>

</semantics>

</math></span><img src="./8de3738e28be985611c994c0ad92cfbd32c12f45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.868ex; height:2.176ex;" alt="{\displaystyle NNF}" loading="lazy"></span>. The iterations examine the offsets in scan order (from left to right, top to bottom), and each undergoes <b>propagation</b> followed by <b>random search</b>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Propagation">Propagation</h3></div>

<p>We attempt to improve <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x,y)}</annotation>

</semantics>

</math></span><img src="./29473ed0c4e838ac9dbe074535e507166c0e9101.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.607ex; height:2.843ex;" alt="{\displaystyle f(x,y)}" loading="lazy"></span> using the known offsets of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x-1,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x-1,y)}</annotation>

</semantics>

</math></span><img src="./cc97900a772f4e3bb0f4d1d4c7fee0d59deaa2d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.61ex; height:2.843ex;" alt="{\displaystyle f(x-1,y)}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x,y-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x,y-1)}</annotation>

</semantics>

</math></span><img src="./0ee896700f42e8bff50acdd26b5d77b1ce1442e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.61ex; height:2.843ex;" alt="{\displaystyle f(x,y-1)}" loading="lazy"></span>, assuming that the patch offsets

are likely to be the same. That is, the algorithm will take new value for <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x,y)}</annotation>

</semantics>

</math></span><img src="./29473ed0c4e838ac9dbe074535e507166c0e9101.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.607ex; height:2.843ex;" alt="{\displaystyle f(x,y)}" loading="lazy"></span> to be <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \arg \min \limits _{(x,y)}{D(f(x,y)),D(f(x-1,y)),D(f(x,y-1))}}">

</mrow>

</munder>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \arg \min \limits _{(x,y)}{D(f(x,y)),D(f(x-1,y)),D(f(x,y-1))}}</annotation>

</semantics>

</math></span><img src="./ee77203c26ce9c7c890a1a29e708e75c8238a0ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:48.981ex; height:4.509ex;" alt="{\displaystyle \arg \min \limits _{(x,y)}{D(f(x,y)),D(f(x-1,y)),D(f(x,y-1))}}" loading="lazy"></span>.

So if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x,y)}</annotation>

</semantics>

</math></span><img src="./29473ed0c4e838ac9dbe074535e507166c0e9101.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.607ex; height:2.843ex;" alt="{\displaystyle f(x,y)}" loading="lazy"></span> has a correct mapping and is in a coherent region <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math></span><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"></span>, then all of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math></span><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"></span> below and to the right of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x,y)}</annotation>

</semantics>

</math></span><img src="./29473ed0c4e838ac9dbe074535e507166c0e9101.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.607ex; height:2.843ex;" alt="{\displaystyle f(x,y)}" loading="lazy"></span> will be filled with the correct mapping. Alternatively, on even iterations, the algorithm search for different direction, fill the new value to be <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \arg \min \limits _{(x,y)}\{D(f(x,y)),D(f(x+1,y)),D(f(x,y+1))\}}">

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \arg \min \limits _{(x,y)}\{D(f(x,y)),D(f(x+1,y)),D(f(x,y+1))\}}</annotation>

</semantics>

</math></span><img src="./84b59b1a7dd2b99f904f4e5fd0d19aece6d39843.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:50.919ex; height:4.509ex;" alt="{\displaystyle \arg \min \limits _{(x,y)}\{D(f(x,y)),D(f(x+1,y)),D(f(x,y+1))\}}" loading="lazy"></span>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Random_search">Random search</h3></div>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{0}=f(x,y)}</annotation>

</semantics>

</math></span><img src="./7f39729c7c0289f09b4a45fcc94234fa2dbfbab0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.887ex; height:2.843ex;" alt="{\displaystyle v_{0}=f(x,y)}" loading="lazy"></span>, we attempt to improve<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x,y)}</annotation>

</semantics>

</math></span><img src="./29473ed0c4e838ac9dbe074535e507166c0e9101.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.607ex; height:2.843ex;" alt="{\displaystyle f(x,y)}" loading="lazy"></span> by testing a sequence of candidate offsets at an exponentially decreasing <a href="Distance" title="Distance">distance</a> from <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{0}}</annotation>

</semantics>

</math></span><img src="./60faad24775635f4722ccc438093dbbfe05f34ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.182ex; height:2.009ex;" alt="{\displaystyle v_{0}}" loading="lazy"></span>

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u_{i}=v_{0}+w\alpha ^{i}R_{i}}</annotation>

</semantics>

</math></span><img src="./05a94d25e5a5341e92dbd0b79441784255134ac6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.765ex; height:3.009ex;" alt="{\displaystyle u_{i}=v_{0}+w\alpha ^{i}R_{i}}" loading="lazy"></span></dd></dl>

<p>where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{i}}</annotation>

</semantics>

</math></span><img src="./db421291be9d0103404ced7495b363437b67b6b1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.564ex; height:2.509ex;" alt="{\displaystyle R_{i}}" loading="lazy"></span> is a uniform random in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [-1,1]\times [-1,1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [-1,1]\times [-1,1]}</annotation>

</semantics>

</math></span><img src="./3173aa20053cede4df692655215123f50b676934.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.762ex; height:2.843ex;" alt="{\displaystyle [-1,1]\times [-1,1]}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math></span><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"></span> is a large window search <a href="Radius" title="Radius">radius</a> which will be set to maximum picture size, and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math></span><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"></span> is a fixed ratio often assigned as 1/2. This part of the algorithm allows the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x,y)}</annotation>

</semantics>

</math></span><img src="./29473ed0c4e838ac9dbe074535e507166c0e9101.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.607ex; height:2.843ex;" alt="{\displaystyle f(x,y)}" loading="lazy"></span> to jump out of local minimum through random process.

</p>

<div class="mw-heading mw-heading3"><h3 id="Halting_criterion">Halting criterion</h3></div>

<p>The often used halting criterion is set the iteration times to be about 4~5. Even with low iteration, the algorithm works well.

</p>

<ul><li><a href="Nearest_neighbor_search" title="Nearest neighbor search">Nearest neighbor search</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://cacm.acm.org/research/the-patchmatch-randomized-matching-algorithm-for-image-manipulation/">"The Patchmatch Randomized Matching Algorithm For Image Manipulation – Communications of the ACM"</a>. 2011-11-01<span class="reference-accessdate">. Retrieved <span class="nowrap">2024-11-30</span></span>.</cite></span>

</li>

</ol></div></div>

<ul><li>Connelly Barnes, Eli Shechtman, Adam Finkelstein, Dan B Goldman(2009), <a rel="nofollow" class="external text" href="http://gfx.cs.princeton.edu/pubs/Barnes_2009_PAR/">PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-12" href="https://en.wikipedia.org/wiki/?title=PatchMatch&oldid=1290020134">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>